Search results for "Assignment problem"
showing 10 items of 30 documents
New exact methods for the time-invariant berth allocation and quay crane assignment problem
2019
Abstract Efficient management of operations in seaport container terminals has become a critical issue, due to the increase in maritime traffic and the strong competition between ports. In this paper we focus on two seaside operational problems: the Berth Allocation Problem and the Quay Crane Assignment Problem, which are considered in an integrated way. For the continuous BACAP problem with time-invariant crane assignment we propose a new mixed integer linear model in which the vessels can be moored at any position on the quay, not requiring any quay discretization. The model is enhanced by adding several families of valid inequalities. The resulting model is able to solve instances with u…
Approximate Algorithm for Fast Capacity Provisioning in WANs with Trade-Off between Performance and Cost under Budget Constraint
2014
Due to the emergence of Software Defined Networking (SDN) with the idea of centralized control over computer networks, the Capacity and Flow Assignment Problem (CFA) may be approached in a classical non-distributed fashion in real-life scenarios. The question arises whether a heuristical approach to this NP-complete problem is of any use in practice.
Optical Routing of Uniform Instances in Cayley Graphs
2001
Abstract Abstract We consider the problem of routing uniform communication instances in Cayley graphs. Such instances consist of all pairs of nodes whose distance is included in a specified set U. We give bounds on the load induced by these instances on the links and for the wavelength assignment problem as well. For some classes of Cayley graphs that have special symmetry property (rotational graphs), we are able to construct routings for uniform instances such that the load is the same for each link of the graph.
A Restricted-Weakly Connected Dominating Set for Role Assignment in a Multichannel MAC for Wireless Mesh Network
2009
International audience; We propose an efficient way of constructing the wireless mesh structure associated with Molecular MAC, a multichannel access method designed for efficient packet forwarding. We base our role assignment on a restricted Weakly Connected Dominating Set structure. After presenting a formal definition of the role assignment problem, we prove its NP-completeness. Then, we propose a centralized 2-approximation algorithm that maximizes the sum of radio link capacities in the molecular structure. Finally, we extend this protocol so that it can operate in a distributed way still providing the same guarantee. This distributed protocol is self-stabilizing thus robust to topology…
Exact and Approximate Algorithms for Two–Criteria Topological Design Problem of WAN with Budget and Delay Constraints
2004
This paper studies the problem of designing wide area networks (WAN). In the paper the two-criteria topology assignment problem with two constraints is considered. The goal is select flow routes, channel capacities and network topology in order to minimize the total average delay per packet and the leasing cost of channels subject to the budget constraint and delay constraint. The problem is NP-complete. Then, the branch and bound method is used to construct the exact algorithm. Also the approximate algorithm is presented. Some computational results are reported. Based on computational experiments, several properties of the considered problem are formulated.
Combinatorial Optimization for Artificial Intelligence Enabled Mobile Network Automation
2021
This chapter discusses combinatorial optimization techniques for enabling intelligent automation in mobile networks. A number of discrete optimization problems pertinent to mobile network automation can be solved effectively using artificial intelligence based combinatorial optimization approaches such as heuristics and metaheuristics. Relevant use-cases include both initial parameter assignment during network roll-out, and continuous optimization of configuration management parameters during network operation and maintenance. We discuss mobile network automation use-cases and motivation for using different heuristics and metaheuristics in designing network optimization algorithms. To this …
Heuristic algorithms for a storage location assignment problem in a chaotic warehouse
2014
The extensive application of emerging technologies is revolutionizing warehouse management. These technologies facilitate working with complex and powerful warehouse management models in which products do not have assigned fixed locations (random storage). Random storage allows the utilization of the available space to be optimized. In this context, and motivated by a real problem, this article presents a model that looks for the optimal allocation of goods in order to maximize the storage space availability within the restrictions of the warehouse. For the proposed model a construction method, a local search algorithm and different metaheuristics have been developed. The introduced algorit…
An Exact Algorithm for the Quadratic Assignment Problem on a Tree
1989
The Tree QAP is a special case of the Quadratic Assignment Problem (QAP) where the nonzero flows form a tree. No condition is required for the distance matrix. This problem is NP-complete and is also a generalization of the Traveling Salesman Problem. In this paper, we present a branch-and-bound algorithm for the exact solution of the Tree QAP based on an integer programming formulation of the problem. The bounds are computed using a Lagrangian relaxation of this formulation. To solve the relaxed problem, we present a Dynamic Programming algorithm which is polynomially bounded. The obtained lower bound is very sharp and equals the optimum in many cases. This fact allows us to employ a redu…
The minimal cost maximum matching of a graph (supplementary remarks)
1971
In addition to the preceding paper, it will be shown that (1) the matching problem is closely related to the linear assignment problem and how (2) this property can be taken advantage of for solving the matching problem.
Labour Scheduling at an Airport Refuelling Installation
1999
We have developed an automatic assignment procedure for labour scheduling at a continously operating airport refuelling installation. Different types of workers are subject to different conditions on the shifts they can do (morning, evening or night), shift lengths, days-off, holidays, terms of contract and working hours. The scheduling process is carried out on a weekly basis, but there are mid-term and long-term conditions and objectives which link each week with the preceding and following weeks. Our package uses firstly a tabu search algorithm to find the best schemes of shifts/days-off to be used to cover the requirements. Secondly, an assignment problem is solved to match the schemes …